home *** CD-ROM | disk | FTP | other *** search
/ Windows Undocumented File Formats / Windows Undocumented File Formats.img / CHAP6 / COMP.C next >
C/C++ Source or Header  |  1997-07-15  |  11KB  |  370 lines
  1. /**********************************************************************
  2.  *
  3.  * PROGRAM: COMP.C
  4.  *
  5.  * PURPOSE: Compress a file using something like Microsoft's derivative on LZ77
  6.  * (i.e., it can be uncompressed using Microsoft's EXPAND.EXE)
  7.  *
  8.  * Copyright 1997, Mike Wallace and Pete Davis
  9.  *
  10.  * Chapter 6, Compression Algorithm and File Formats, from Undocumented Windows
  11.  * File Formats, published by R&D Books, an imprint of Miller Freeman, Inc.
  12.  *
  13.  **********************************************************************/
  14.  
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17. #include <string.h>
  18. #include "decomp.h"
  19.  
  20. #define WINSIZE  4096
  21. #define MAXLEN   18
  22.  
  23. #define COMP_CODE(x,y) ((((x-3) & 0x0F) << 8) + (((y - 0x10) & \
  24.                        0x0F00) << 4) + ((y - 0x10) & 0x00FF))
  25.  
  26. #define LOBYTE(x) ((unsigned char)(x))
  27. #define HIBYTE(x) ((unsigned char)(((unsigned short)(x) >> 8) & 0xFF))
  28.  
  29. #define DROP_INDEX(x) (x == 0) ? (WINSIZE - 1) : (x - 1)
  30. #define ADD_INDEX(x)  ((x + 1) == WINSIZE) ? 0 : (x + 1)
  31.  
  32. /* This is our Compression Window */
  33. unsigned char Window[WINSIZE];
  34.  
  35. /***************************************************
  36.   Set bit number "bit" in byte "byte"
  37. ****************************************************/
  38. void BitSet(int bit, char *byte)
  39. {
  40.  
  41.    short result = 1;
  42.  
  43.    /* make sure bit range is 0,..,7 */
  44.    if (bit < 0) bit = 0;
  45.    else if (bit > 7) bit = 7;
  46.  
  47.    while (bit--)
  48.       result *= 2;
  49.  
  50.    *byte = result | *byte;
  51.  
  52. } /* BitSet - end */
  53.  
  54.  
  55. /*************************************************
  56.   InBetween - detects if lower <= target <= higher
  57. **************************************************/ 
  58. int InBetween(int lower, int higher, int target)
  59. {
  60.  
  61.   if(higher < lower)
  62.      higher += WINSIZE;
  63.   if((lower <= target) && (target <= higher))
  64.      return 1;
  65.   else
  66.      return 0;
  67.  
  68. } /* InBetween - end */
  69.  
  70.  
  71. /*************************************************
  72.   Force FlagByte and DataBytes to print out
  73. **************************************************/ 
  74. void WriteFlagByte(FILE *outfile)
  75. {
  76.  
  77.    int index = 0;
  78.  
  79.    if(FlagCount > 0) {
  80.       DataBytes[DataCount] = '\0';
  81.       fputc(FlagByte, outfile);
  82.       for (; index < DataCount ; ++index)
  83.          fprintf(outfile, "%c", DataBytes[index]);
  84.       DataCount = FlagCount = 0;
  85.       FlagByte = '\0';
  86.       for (index = 0; index < 17; ++index)
  87.          DataBytes[index] = ' ';
  88.    }
  89.  
  90. } /* WriteFlagByte - end */
  91.  
  92.  
  93. /*************************************************
  94.   Check if FlagByte is full and should be printed out
  95. **************************************************/ 
  96. void CheckFlagByte(FILE *outfile)
  97. {
  98.  
  99.    ++DataCount;
  100.    if(++FlagCount == 8)
  101.      WriteFlagByte( outfile );
  102.  
  103. } /* CheckFlagByte - end */
  104.  
  105.  
  106. /*************************************************
  107.   Saves an uncompressed data byte
  108. **************************************************/ 
  109. void GetNextChar( int *CurrPos, FILE *infile)
  110. {
  111.  
  112.    unsigned char ch;
  113.  
  114.    fread(&ch, sizeof(char), 1, infile);
  115.    if (!feof(infile))
  116.       Window[*CurrPos = ADD_INDEX(*CurrPos)] = ch;
  117.  
  118. } /* GetNextChar - end */
  119.  
  120.  
  121. /*************************************************
  122.   Unreads the last character read
  123. **************************************************/ 
  124. void UnreadChar(unsigned char ch, FILE *infile, int *CurrPos, 
  125.                 unsigned char ch2)
  126. {
  127.  
  128.    ungetc( ch, infile);
  129.    Window[*CurrPos] = ch2;
  130.    *CurrPos = DROP_INDEX(*CurrPos);
  131.  
  132. } /* UnreadChar - end */
  133.  
  134.  
  135. /*************************************************
  136.   Saves an uncompressed data byte
  137. **************************************************/ 
  138. void SaveUncompByte(unsigned char ch, FILE *outfile)
  139. {
  140.  
  141.    BitSet(FlagCount, &FlagByte);
  142.    DataBytes[DataCount] = ch;
  143.    CheckFlagByte( outfile );
  144.  
  145. } /* SaveUncompByte - end */
  146.  
  147.  
  148. /*************************************************
  149.   Compresses the data using Microsoft's LZ77
  150. derivative (Zeck).
  151. **************************************************/ 
  152. void Compress(FILE *infile, FILE *outfile)
  153. {
  154.  
  155.    int count=0, shifter=0, CurrPos=0;
  156.    int SavePos=0, iCompCode = 0, offset = 0;
  157.    int newPos = 0;
  158.    unsigned char ch;
  159.    int bestcount = 0, bestoffset = 0;
  160.    char oldchars[3];
  161.  
  162.    FlagCount = 0;
  163.    DataCount = 0;
  164.    FlagByte  = '\0';
  165.  
  166.    for (count = 0; count < WINSIZE; count ++)
  167.       Window[count] = ' ';
  168.  
  169.    rewind( infile );
  170.  
  171.    /* Go through input file until we're done */
  172.    fread(&ch, sizeof(char), 1, infile);
  173.    Window[CurrPos] = ch;
  174.    while (!feof(infile)) {
  175.  
  176.       /* if less than 3 chars from end, just write out remainder */
  177.       if((InfileSize - ftell(infile)) < 2) {
  178.          SaveUncompByte( Window[CurrPos], outfile);
  179.          GetNextChar( &CurrPos, infile);
  180.          continue;
  181.       } 
  182.  
  183.       /* Find previous occurrence of character in window */
  184.       for (count = 1, shifter = DROP_INDEX(CurrPos);
  185.          (Window[shifter] != Window[CurrPos]) && (count < WINSIZE);
  186.          ++count, shifter = DROP_INDEX(shifter)) {}
  187.  
  188.       /* check if char is unique so far in input file */
  189.       if(count == WINSIZE) {
  190.          SaveUncompByte( Window[CurrPos], outfile);
  191.          GetNextChar( &CurrPos, infile);
  192.          continue;
  193.       }
  194.       else {
  195.  
  196.          /* find out how many characters match */
  197.          SavePos = CurrPos;
  198.          oldchars[2] = oldchars[0] = Window[ADD_INDEX(CurrPos)];
  199.          GetNextChar( &CurrPos, infile);
  200.          for(count = 1, offset=shifter, shifter = ADD_INDEX(shifter);
  201.             (!feof(infile)) && (Window[shifter] == Window[CurrPos]) && 
  202.             (count < MAXLEN);) {
  203.             ++count;
  204.             if(count == 2)
  205.                oldchars[1] = Window[ADD_INDEX(CurrPos)];
  206.             oldchars[2] = Window[ADD_INDEX(CurrPos)];
  207.             GetNextChar( &CurrPos, infile);
  208.             shifter = ADD_INDEX(shifter); 
  209.          }
  210.  
  211.          /* Since this is the first match, save it as the best so far */
  212.          bestcount  = count;
  213.          bestoffset = offset;
  214.  
  215.          if(((Window[shifter] != Window[CurrPos]) || (count == MAXLEN)) &&
  216.             (!feof(infile)))
  217.             UnreadChar( Window[CurrPos], infile, &CurrPos, oldchars[2]);
  218.  
  219.          /* Now find the best match for the string in the window */
  220.          shifter = DROP_INDEX( offset );
  221.          while((shifter != CurrPos) && (bestcount < MAXLEN) &&
  222.             (!InBetween( SavePos, CurrPos, shifter))) {
  223.  
  224.             for( ; (shifter != CurrPos) && (Window[shifter] != Window[SavePos]);
  225.                shifter = DROP_INDEX(shifter)) {}
  226.             if(shifter == CurrPos)
  227.                continue;
  228.             for(count = 0, offset = shifter, newPos = SavePos;
  229.                (!feof(infile)) && (Window[shifter] == Window[newPos]) &&
  230.                (count < MAXLEN); ++count, newPos = ADD_INDEX(newPos)) {
  231.                if (count >= (bestcount - 1)) {
  232.                   if(count == 1)
  233.                      oldchars[1] = Window[ADD_INDEX(CurrPos)];
  234.                   oldchars[2] = Window[ADD_INDEX(CurrPos)];
  235.                   GetNextChar( &CurrPos, infile );
  236.                }
  237.                shifter = ADD_INDEX(shifter);
  238.             }
  239.  
  240.             if(((count >= MAXLEN) || ((Window[shifter] != Window[newPos]) && 
  241.                (count >= bestcount))) && (!feof(infile)))
  242.                UnreadChar( Window[CurrPos], infile, &CurrPos, oldchars[2]);
  243.  
  244.             if(count > bestcount) {
  245.                bestcount = count;
  246.                bestoffset = offset;
  247.             }
  248.             shifter = DROP_INDEX( offset );
  249.  
  250.          } /* while(shifter != CurrPos) */
  251.  
  252.          if(!feof(infile))
  253.             GetNextChar( &CurrPos, infile );
  254.  
  255.          count = bestcount;
  256.          offset = bestoffset;
  257.  
  258.          /* if count < 3, then not enough chars to compress */
  259.          if (count < 3) {
  260.             SaveUncompByte( Window[SavePos], outfile);
  261.             fseek(infile, ftell(infile) - count, 0);
  262.             Window[SavePos = ADD_INDEX(SavePos)] = oldchars[0];
  263.             CurrPos = DROP_INDEX(CurrPos);
  264.             if (count == 2) {
  265.                Window[ADD_INDEX(SavePos)] = oldchars[1];
  266.                CurrPos = DROP_INDEX(CurrPos);
  267.             }
  268.  
  269.          }
  270.          else {
  271.             iCompCode = COMP_CODE(count, offset);
  272.             DataBytes[DataCount]   = LOBYTE(iCompCode);
  273.             DataBytes[++DataCount] = HIBYTE(iCompCode);
  274.             CheckFlagByte( outfile );
  275.  
  276.             if (!feof(infile))
  277.                 UnreadChar( Window[CurrPos], infile, &CurrPos, oldchars[2]);
  278.          }
  279.  
  280.          if((!feof(infile)) && (count <= MAXLEN))
  281.             GetNextChar( &CurrPos, infile);
  282.  
  283.       }
  284.  
  285.    } /* while - end */
  286.  
  287.    WriteFlagByte( outfile );
  288.  
  289. } /* Compress - end */
  290.  
  291. /***************************************************
  292.   Write the header that exists at the beginning of 
  293.   every file compressed using MS's Zeck compression
  294. ****************************************************/
  295. void WriteHeader(FILE *infile, FILE *outfile)
  296. {
  297.  
  298.    COMPHEADER CompHeader;
  299.  
  300.    CompHeader.Magic1 = MAGIC1;
  301.    CompHeader.Magic2 = MAGIC2;
  302.    CompHeader.Is41 = 0x41;
  303.    CompHeader.FileFix = '\0';  /* This stores the original last */
  304.                                /* char. of the input filename   */
  305.  
  306.    fseek( infile, 0L, 2);
  307.    CompHeader.DecompSize = InfileSize = ftell(infile);
  308.    rewind( infile );
  309.  
  310.    rewind( outfile);
  311.     
  312.    fwrite(&CompHeader, sizeof(CompHeader), 1, outfile);
  313.  
  314.    Compress(infile, outfile);
  315.  
  316. } /* WriteHeader - end */
  317.  
  318.  
  319. /***************************************************
  320.   Show usage.
  321. ****************************************************/
  322. void Usage( void )
  323. {
  324.  
  325.    printf("Usage:\n");
  326.    printf(" COMP file1.ext file2.ext\n\n");
  327.    printf("   file1.ext - Name of uncompressed file\n");
  328.    printf("   file2.ext - Name of compressed file\n\n");
  329.  
  330. } /* Usage - end */
  331.  
  332.  
  333. /***************************************************
  334.   Open the input and output files, and call routine
  335.   to compress the data.
  336. ****************************************************/
  337. int main(int argc, char *argv[])
  338. {
  339.  
  340.    char filename[128];
  341.    FILE *infile, *outfile;
  342.  
  343.    if (argc != 3) {
  344.       Usage();
  345.       return EXIT_FAILURE;
  346.    }
  347.  
  348.    strcpy(filename, argv[1]);
  349.    if ((infile = fopen(filename, "rb")) == NULL) {
  350.       printf("%s does not exist\n", filename);
  351.       return(EXIT_FAILURE);
  352.    }
  353.  
  354.    strcpy(filename, argv[2]);
  355.    if ((outfile=fopen(filename, "wb+")) == NULL) {
  356.       printf("Error opening destination file\n");
  357.       return(EXIT_FAILURE);
  358.    }
  359.  
  360.    WriteHeader(infile, outfile);
  361.    fclose(infile);
  362.    fclose(outfile);
  363.  
  364.    return(EXIT_SUCCESS);
  365.  
  366. } /* main - end */
  367.  
  368. /* comp.c - end */
  369.  
  370.